/*
 【入门】当总统
  题目描述
    小明想当丑国的总统，丑国大选是按各州的投票结果来确定最终的结果的，
    如果得到超过一半的州的支持就可以当选，而每个州的投票结果又是由该州选民投票产生的，
    如果某个州超过一半的选民支持小明，则他将赢得该州的支持。
    现在给出每个州的选民人数，请问小明至少需要赢得多少选民的支持才能当选？
  输入
    输入一个整数 n，代表有 n（1 < n < 100）组数据；
    接下来是 n 组数据, 每组数据的格式如下:
      第一行是一个整数 m (1 <= m <= 101), 表示丑国的州数。
      接下来包括 m 个正整数，分别表示每个州的选民数，每个州的选民数不超过 100。
  输出
    对于每组数据输出一行，表示小明至少需要赢得支持的选民数。
  样例输入
    2
    3
    5 7 5
    6
    8 22 72 45 14 45
  样例输出
    6
    48
*/

#include <bits/stdc++.h>

using namespace std;

int a[101][102] = {};
int m[101] = {};

int main() {
    int n;

    cin >> n;

    for (int i = 1; i <= n; i++) {
        int m, a[102];

        cin >> m;
        for (int j = 1; j <= m; j++) {
            cin >> a[j];   // a[j] 表示第 j 个州的选民数
        }

        // 对 a[1] ~ a[m] 按从小到大的顺序进行排序
        sort(a + 1, a + m + 1);

        // 挑选人数最少的 m / 2 + 1 个州，分别找出这些州中"一半 +1" 的选民数，并进行累加
        int xi = 0;
        for (int j = 1; j <= m / 2 + 1; j++) {
            xi = xi + a[j] / 2 + 1;
        }
        cout << xi << endl;
    }

    return 0;
}